{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Days to Disconnect Island"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array #matrix #strongly-connected-component"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组 #矩阵 #强连通分量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使陆地分离的最少天数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>m x n</code> ，由若干 <code>0</code> 和 <code>1</code> 组成的二维网格 <code>grid</code> ，其中 <code>1</code> 表示陆地， <code>0</code> 表示水。<strong>岛屿</strong> 由水平方向或竖直方向上相邻的 <code>1</code> （陆地）连接形成。</p>\n",
    "\n",
    "<p>如果 <strong>恰好只有一座岛屿 </strong>，则认为陆地是 <strong>连通的</strong> ；否则，陆地就是 <strong>分离的</strong> 。</p>\n",
    "\n",
    "<p>一天内，可以将 <strong>任何单个</strong> 陆地单元（<code>1</code>）更改为水单元（<code>0</code>）。</p>\n",
    "\n",
    "<p>返回使陆地分离的最少天数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/24/land1.jpg\" style=\"width: 500px; height: 169px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>至少需要 2 天才能得到分离的陆地。\n",
    "将陆地 grid[1][1] 和 grid[0][2] 更改为水，得到两个分离的岛屿。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/24/land2.jpg\" style=\"width: 404px; height: 85px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,1]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>如果网格中都是水，也认为是分离的 ([[1,1]] -&gt; [[0,0]])，0 岛屿。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 30</code></li>\n",
    "\t<li><code>grid[i][j]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-days-to-disconnect-island](https://leetcode.cn/problems/minimum-number-of-days-to-disconnect-island/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-days-to-disconnect-island](https://leetcode.cn/problems/minimum-number-of-days-to-disconnect-island/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1,1,0],[0,1,1,0],[0,0,0,0]]', '[[1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        uf = UnionFind(m*n)\n",
    "        cnt = 0\n",
    "        lst = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    for x, y in [[i+1, j], [i, j+1]]:\n",
    "                        if 0<=x<m and 0<=y<n and grid[x][y]:\n",
    "                            uf.union(i*n+j, x*n+y)\n",
    "                    cnt += 1\n",
    "                    lst.append([i, j])\n",
    "        if cnt <= 1:\n",
    "            return cnt\n",
    "        roots = [uf.find(i) for i in range(m*n) if grid[i//n][i%n]]\n",
    "        if len(set(roots)) > 1:\n",
    "            return 0\n",
    "        \n",
    "        for a, b in lst:\n",
    "            grid[a][b] = 0\n",
    "            \n",
    "            uf = UnionFind(m * n)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j]:\n",
    "                        for x, y in [[i + 1, j], [i, j + 1]]:\n",
    "                            if 0 <= x < m and 0 <= y < n and grid[x][y]:\n",
    "                                uf.union(i * n + j, x * n + y)\n",
    "            roots = [uf.find(i) for i in range(m * n) if grid[i // n][i % n]]\n",
    "            if len(set(roots)) > 1:\n",
    "                return 1\n",
    "            \n",
    "            grid[a][b] = 1\n",
    "        \n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        d=[[0,1],[1,0],[-1,0],[0,-1]]\n",
    "        def dfs(x,y,l):\n",
    "            if x<0 or x>=m or y<0 or y>=n:\n",
    "                return \n",
    "            if l[x][y]==0:\n",
    "                return \n",
    "            l[x][y]=0\n",
    "            for a,b in d:\n",
    "                dfs(x+a,y+b,l)\n",
    "        def isconnection():\n",
    "            g=copy.deepcopy(grid)\n",
    "            find=False\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if g[i][j]==1:\n",
    "                        if find:\n",
    "                            return False\n",
    "                        find=True\n",
    "                        dfs(i,j,g)\n",
    "            if not find:\n",
    "                return False\n",
    "            return True\n",
    "        if not isconnection():\n",
    "            return 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    grid[i][j]=0\n",
    "                    #print(grid)\n",
    "                    if not isconnection():\n",
    "                        return 1\n",
    "                    grid[i][j]=1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x: int, y: int):\n",
    "            grid[x][y] = 2\n",
    "            for tx, ty in [(x, y + 1), (x + 1, y), (x, y - 1), (x - 1, y)]:\n",
    "                if 0 <= tx < n and 0 <= ty < m and grid[tx][ty] == 1:\n",
    "                    dfs(tx, ty)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 1:\n",
    "                        cnt += 1\n",
    "                        dfs(i, j)\n",
    "            # 还原\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "        \n",
    "        n, m = len(grid), len(grid[0])\n",
    "        \n",
    "        # 岛屿数量不为 1，陆地已经分离\n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    grid[i][j] = 0\n",
    "                    if count() != 1:\n",
    "                        # 更改一个陆地单元为水单元后陆地分离\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        \n",
    "        return 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x: int, y: int):\n",
    "            grid[x][y] = 2\n",
    "            for tx, ty in [(x, y + 1), (x + 1, y), (x, y - 1), (x - 1, y)]:\n",
    "                if 0 <= tx < n and 0 <= ty < m and grid[tx][ty] == 1:\n",
    "                    dfs(tx, ty)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 1:\n",
    "                        cnt += 1\n",
    "                        dfs(i, j)\n",
    "            # 还原\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "        \n",
    "        n, m = len(grid), len(grid[0])\n",
    "        \n",
    "        # # 岛屿数量不为 1，陆地已经分离\n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    grid[i][j] = 0\n",
    "                    if count() != 1:\n",
    "                        # 更改一个陆地单元为水单元后陆地分离\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        \n",
    "        return 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m, n, mn = len(grid), len(grid[0]), len(grid) * len(grid[0])\n",
    "        neighbors, degs = [[] for _ in range(mn)], [-1] * mn\n",
    "        steps = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    for step in steps:\n",
    "                        ii, jj = i + step[0], j + step[1]\n",
    "                        if ii >= 0 and ii < m and jj >= 0 and jj < n and grid[ii][jj] == 1:\n",
    "                            neighbors[i * n + j].append(ii * n + jj)\n",
    "                    degs[i * n + j] = len(neighbors[i * n +j])\n",
    "        def myCon():\n",
    "            parent, rank = list(range(mn)), [0] * mn\n",
    "            def myFind(x):\n",
    "                if x != parent[x]:\n",
    "                    parent[x] = myFind(parent[x])\n",
    "                return parent[x]\n",
    "            def myUnion(x, y):\n",
    "                px, py = myFind(x), myFind(y)\n",
    "                if px == py: return\n",
    "                if rank[px] > rank[py]:\n",
    "                    parent[py] = px\n",
    "                elif rank[px] < rank[py]:\n",
    "                    parent[px] = py\n",
    "                else:\n",
    "                    parent[py] = px\n",
    "                    rank[px] += 1\n",
    "                return\n",
    "            for i in range(mn):\n",
    "                if degs[i] > -1:\n",
    "                    for j in neighbors[i]:\n",
    "                        myUnion(i, j)\n",
    "            s = set()\n",
    "            for i in range(mn):\n",
    "                if degs[i] > -1:\n",
    "                    s.add(myFind(i))\n",
    "            return len(s) == 1\n",
    "        # Tarjan\n",
    "        def myCut():\n",
    "            dfn, low = [-1] * mn, [-1] * mn\n",
    "            time = [0]\n",
    "            for i in range(mn):\n",
    "                if degs[i] > 0:\n",
    "                    break\n",
    "            cut = set()\n",
    "            def dfs(x, fa):\n",
    "                dfn[x] = low[x] = time[0]\n",
    "                time[0] += 1\n",
    "                children = 0\n",
    "                for y in neighbors[x]:\n",
    "                    if y == fa: continue\n",
    "                    if dfn[y] != -1:\n",
    "                        low[x] = min(low[x], dfn[y])\n",
    "                    else:\n",
    "                        dfs(y, x)\n",
    "                        low[x] = min(low[x], low[y])\n",
    "                        children += 1\n",
    "                        if fa == -1 and children > 1:\n",
    "                            cut.add(x)\n",
    "                        if fa != -1 and low[y] >= dfn[x]:\n",
    "                            cut.add(x)\n",
    "                return\n",
    "            dfs(i, -1)\n",
    "            return len(cut) > 0\n",
    "\n",
    "        if not myCon():\n",
    "            return 0\n",
    "        if myCut():\n",
    "            return 1\n",
    "        else:\n",
    "            if degs.count(-1) == mn - 1:\n",
    "                return 1\n",
    "            else:\n",
    "                return 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x: int, y: int):\n",
    "            grid[x][y] = 2\n",
    "            for tx, ty in [(x, y + 1), (x + 1, y), (x, y - 1), (x - 1, y)]:\n",
    "                if 0 <= tx < n and 0 <= ty < m and grid[tx][ty] == 1:\n",
    "                    dfs(tx, ty)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 1:\n",
    "                        cnt += 1\n",
    "                        dfs(i, j)\n",
    "            # 还原\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "        \n",
    "        n, m = len(grid), len(grid[0])\n",
    "        \n",
    "        # 岛屿数量不为 1，陆地已经分离\n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    grid[i][j] = 0\n",
    "                    if count() != 1:\n",
    "                        # 更改一个陆地单元为水单元后陆地分离\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        \n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x:int, y:int):\n",
    "            grid[x][y] = 2\n",
    "            for tx,ty in [(x,y+1),(x+1,y),(x,y-1),(x-1,y)]:\n",
    "                if 0 <= tx < n and 0 <= ty < m and grid[tx][ty] == 1:\n",
    "                    dfs(tx,ty)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 1:\n",
    "                        cnt += 1\n",
    "                        dfs(i,j)\n",
    "            \n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "        \n",
    "        n , m = len(grid), len(grid[0])\n",
    "\n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    grid[i][j] = 0\n",
    "                    if count() != 1:\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x:int, y:int):\n",
    "            grid[x][y] = 2\n",
    "            for tx,ty in [(x,y+1),(x+1,y),(x,y-1),(x-1,y)]:\n",
    "                if 0 <= tx < n and 0 <= ty < m and grid[tx][ty] == 1:\n",
    "                    dfs(tx,ty)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 1:\n",
    "                        cnt += 1\n",
    "                        dfs(i,j)\n",
    "            \n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "        \n",
    "        n , m = len(grid), len(grid[0])\n",
    "\n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    grid[i][j] = 0\n",
    "                    if count() != 1:\n",
    "                        # 更改一个陆地单元为水单元后陆地分离\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0]) \n",
    "        def dfs(x, y):\n",
    "            for dx, dy in [[x + 1, y], [x - 1, y],[x, y - 1], [x, y + 1]]:\n",
    "                if 0 <= dx < m and 0 <= dy < n:\n",
    "                    if grid[dx][dy] == 1:\n",
    "                        grid[dx][dy] = 2\n",
    "                        dfs(dx, dy)\n",
    "        def check():\n",
    "            cnt = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 1:\n",
    "                        cnt += 1\n",
    "                        dfs(i, j)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "            \n",
    "        if check() != 1:\n",
    "            return 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    grid[i][j] = 0\n",
    "                    if check() != 1:\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x:int, y:int):\n",
    "            grid[x][y] = 2\n",
    "            for tx,ty in [(x,y+1),(x+1,y),(x,y-1),(x-1,y)]:\n",
    "                if 0 <= tx < n and 0 <= ty < m and grid[tx][ty] == 1:\n",
    "                    dfs(tx,ty)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 1:\n",
    "                        cnt += 1\n",
    "                        dfs(i,j)\n",
    "            \n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "        \n",
    "        n , m = len(grid), len(grid[0])\n",
    "\n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    grid[i][j] = 0\n",
    "                    if count() != 1:\n",
    "                        # 更改一个陆地单元为水单元后陆地分离\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        def dfs(x, y):\n",
    "            grid[x][y] = 2\n",
    "            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:\n",
    "                    dfs(nx, ny)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 1:\n",
    "                        dfs(i, j)\n",
    "                        cnt += 1\n",
    "            \n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "            \n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    grid[i][j] = 2\n",
    "                    if count() != 1:\n",
    "                        return 1\n",
    "        return 2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        def count(grid):\n",
    "            res = 0\n",
    "            used = [[0] * col for _ in range(row)]\n",
    "            for i in range(row):\n",
    "                for j in range(col):\n",
    "                    if grid[i][j] == 1 and used[i][j] == 0:\n",
    "                        used[i][j] = 1\n",
    "                        dfs(i, j, used)\n",
    "                        res += 1\n",
    "            return res\n",
    "        \n",
    "        def dfs(i, j, used):\n",
    "            for m, n in [(i-1, j), (i, j-1), (i+1, j), (i, j+1)]:\n",
    "                if 0 <= m < row and 0 <= n < col and used[m][n] == 0 and grid[m][n] == 1:\n",
    "                    used[m][n] = 1\n",
    "                    dfs(m, n, used)\n",
    "            return\n",
    "        \n",
    "        island_num = count(grid)\n",
    "        if island_num != 1: return 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    grid[i][j] = 0\n",
    "                    island_num = count(grid)\n",
    "                    if island_num != 1: return 1\n",
    "                    grid[i][j] = 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        def dfs(x, y):\n",
    "            grid[x][y] = 2\n",
    "            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:\n",
    "                    dfs(nx, ny)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 1:\n",
    "                        dfs(i, j)\n",
    "                        cnt += 1\n",
    "            \n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "            return cnt\n",
    "            \n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    grid[i][j] = 2\n",
    "                    if count() != 1:\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        return 2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x, y):\n",
    "            grid[x][y] = 2\n",
    "\n",
    "            for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:\n",
    "                if 0 <= nx <n and 0<=ny<m and grid[nx][ny] == 1:\n",
    "                    dfs(nx, ny)\n",
    "        m, n = len(grid[0]), len(grid)\n",
    "        \n",
    "        def count():\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 1:\n",
    "                        cnt += 1\n",
    "                        dfs(i, j)\n",
    "                        # print(grid)\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] == 2:\n",
    "                        grid[i][j] = 1\n",
    "\n",
    "            return cnt\n",
    "        # print(count())\n",
    "        if count() != 1:\n",
    "            return 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    grid[i][j] = 0\n",
    "                    if count() != 1:\n",
    "                        # 更改一个陆地单元为水单元后陆地分离\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "\n",
    "        return 2 \n",
    "                \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0]) \n",
    "        clk = 0 \n",
    "        def dfs(i, j):\n",
    "            nonlocal clk \n",
    "            clk += 1\n",
    "            vis[i][j] = 1\n",
    "            for [ni,nj] in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:\n",
    "                if 0<=ni<m and 0<=nj<n and grid[ni][nj] == 1 and not vis[ni][nj]:\n",
    "                    dfs(ni,nj)\n",
    "            vis[i][j] = 2 \n",
    "            clk += 1 \n",
    "        comp = 0 \n",
    "        vis = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and not vis[i][j]:\n",
    "                    dfs(i,j)\n",
    "                    comp+=1\n",
    "        if comp > 1:\n",
    "            return 0 \n",
    "        if clk // 2 <= 2:\n",
    "            return clk // 2 \n",
    "        \n",
    "        amt = clk // 2\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    vis = [[0] * n for _ in range(m)] \n",
    "                    grid[i][j] = 0 \n",
    "                    clk = 0\n",
    "                    for x in range(m):\n",
    "                        flag = 0\n",
    "                        for y in range(n):\n",
    "                            if grid[x][y] == 1:\n",
    "                                dfs(x, y)\n",
    "                                flag = 1\n",
    "                                break \n",
    "                        if flag:\n",
    "                            break \n",
    "                    #print(clk//2, amt, i, j)\n",
    "                    if clk // 2 < amt - 1:\n",
    "                        return 1\n",
    "                    grid[i][j] = 1\n",
    "        return 2  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        tot = 0 \n",
    "        m, n = len(grid), len(grid[0]) \n",
    "        vis = [[0] * n for _ in range(m)]\n",
    "        clk = 0\n",
    "        def dfs(i, j):\n",
    "            nonlocal clk \n",
    "            vis[i][j] = 1\n",
    "            clk += 1 \n",
    "            for [ni,nj] in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:\n",
    "                if 0<=ni<m and 0<=nj<n and grid[ni][nj] == 1:\n",
    "                    if not vis[ni][nj]:\n",
    "                        dfs(ni,nj) \n",
    "            vis[i][j] = 2\n",
    "            clk +=1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and not vis[i][j]:\n",
    "                    dfs(i, j) \n",
    "                    tot += 1\n",
    "        if tot == 0 or tot > 1:\n",
    "            return 0 \n",
    "        if clk // 2 == 2:\n",
    "            return 2\n",
    "        if clk // 2 == 1:\n",
    "            return 1 \n",
    "    \n",
    "        data = [i for i in range(n*m+1)]\n",
    "        def find(x):\n",
    "            if x == data[x]:\n",
    "                return x\n",
    "            else:\n",
    "                data[x] = find(data[x])\n",
    "                return data[x]\n",
    "        def un(x, y):\n",
    "            fx,fy = find(x),find(y)\n",
    "            if fx == fy:\n",
    "                return False \n",
    "            else:\n",
    "                data[fy] = fx\n",
    "                return True  \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    scnt = clk//2-1\n",
    "                    data = [i for i in range(n*m+1)]\n",
    "                    for x in range(m):\n",
    "                        for y in range(n):\n",
    "                            if grid[x][y] == 1 and (x,y)!= (i,j):\n",
    "                                for [nx,ny] in [[x+1,y],[x,y+1]]:\n",
    "                                    if 0<=nx<m and 0<=ny<n and grid[nx][ny] == 1 and (nx, ny) != (i, j):\n",
    "                                        if un(x*n+y, nx*n+ny):\n",
    "                                            scnt -= 1\n",
    "                            \n",
    "                    if scnt > 1:\n",
    "                        #print(scnt, i,j)\n",
    "                        return 1\n",
    "        return 2 \n",
    "                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.sz = [1] * n\n",
    "        self.comp_cnt = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.fa[x]:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def unite(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y:\n",
    "            if self.sz[x] < self.sz[y]:\n",
    "                x, y = y, x\n",
    "            self.fa[y] = x\n",
    "            self.sz[x] += self.sz[y]\n",
    "            self.comp_cnt -= 1\n",
    "\n",
    "    def connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        tot = m * n\n",
    "        uf = UF(tot)\n",
    "\n",
    "        mp = lambda t: t[0] * n + t[1]\n",
    "\n",
    "        zeros = 0\n",
    "        sr, sc = -1, -1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    zeros += 1\n",
    "                else:\n",
    "                    sr, sc = i, j\n",
    "                    for ni, nj in (i + 1, j), (i, j + 1):\n",
    "                        if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:\n",
    "                            uf.unite(mp((i, j)), mp((ni, nj)))\n",
    "\n",
    "        if uf.comp_cnt - zeros != 1: return 0 # no island or more than one island\n",
    "        if uf.comp_cnt == tot: return 1 # only one grid is 1\n",
    "\n",
    "        dfn = defaultdict(int)\n",
    "        low = defaultdict(int)\n",
    "        time = 1\n",
    "\n",
    "        def tarjan(x, y, fa):\n",
    "            nonlocal time\n",
    "            dfn[(x, y)] = low[(x, y)] = time\n",
    "            time += 1\n",
    "\n",
    "            cnt = 0\n",
    "            for dx, dy in pairwise([-1, 0, 1, 0, -1]):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1 and (nx, ny) != fa:\n",
    "                    if not dfn[(nx, ny)]:\n",
    "                        cnt += 1\n",
    "                        if tarjan(nx, ny, (x, y)): return True\n",
    "                        low[(x, y)] = min(low[(x, y)], low[(nx, ny)])\n",
    "                        if dfn[(x, y)] <= low[(nx, ny)]:\n",
    "                            if (x, y) != (sr, sc) or cnt > 1:\n",
    "                                return True\n",
    "                    else:\n",
    "                        low[(x, y)] = min(low[(x, y)], dfn[(nx, ny)])\n",
    "            return False\n",
    "        # tarjan(sr, sc, (-1, -1))\n",
    "        # print(dfn)\n",
    "        # print(low)\n",
    "        # print(sr, sc)\n",
    "        return 1 if tarjan(sr, sc, (-1, -1)) else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        new_map = copy.deepcopy(grid)\n",
    "        m , n = len(grid) , len(grid[0])\n",
    "        direction = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        cnt = 0\n",
    "        \n",
    "        def dfs(i,j):\n",
    "            nonlocal cnt\n",
    "            cnt += 1\n",
    "            new_map[i][j] = 0\n",
    "            for di , dj in direction:\n",
    "                ni , nj = i + di , j + dj\n",
    "                if 0 <= ni < m and 0 <= nj < n and new_map[ni][nj] == 1:\n",
    "                    dfs(ni,nj)\n",
    "\n",
    "        val = 0\n",
    "        start = None\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if new_map[i][j] == 1:\n",
    "                    val += 1\n",
    "                    dfs(i,j)\n",
    "                    if not start:\n",
    "                        start = (i,j)\n",
    "\n",
    "        if val > 1:\n",
    "            return 0\n",
    "        \n",
    "        if cnt <= 2:return cnt\n",
    "        low = defaultdict(int)\n",
    "        dfn = defaultdict(int)\n",
    "\n",
    "        def targan(node,parent,deep):\n",
    "\n",
    "            low[node] = dfn[node] = deep\n",
    "            i , j = node\n",
    "            x = 0\n",
    "            for di , dj in direction:\n",
    "                ni , nj = i + di , j + dj\n",
    "                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:\n",
    "                    child = (ni,nj)\n",
    "                    if dfn[child] == 0:\n",
    "                        x += 1\n",
    "                        if targan(child,node,deep+1):\n",
    "                            return True\n",
    "                        low[node] = min(low[node],low[child])\n",
    "                        if dfn[node] <= low[child]:\n",
    "                            if x >= 2 or node != start:\n",
    "                                return True\n",
    "                    else:\n",
    "                        low[node] = min(low[node],dfn[child])\n",
    "            return False\n",
    "\n",
    "        if targan(start,None,1):\n",
    "            return 1\n",
    "        return 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.sz = [1] * n\n",
    "        self.comp_cnt = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.fa[x]:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def unite(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y:\n",
    "            if self.sz[x] < self.sz[y]:\n",
    "                x, y = y, x\n",
    "            self.fa[y] = x\n",
    "            self.sz[x] += self.sz[y]\n",
    "            self.comp_cnt -= 1\n",
    "\n",
    "    def connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        tot = m * n\n",
    "        uf = UF(tot)\n",
    "\n",
    "        mp = lambda t: t[0] * n + t[1]\n",
    "\n",
    "        zeros = 0\n",
    "        sr, sc = -1, -1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    zeros += 1\n",
    "                else:\n",
    "                    sr, sc = i, j\n",
    "                    for ni, nj in (i + 1, j), (i, j + 1):\n",
    "                        if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:\n",
    "                            uf.unite(mp((i, j)), mp((ni, nj)))\n",
    "\n",
    "        if uf.comp_cnt - zeros != 1: return 0 # no island or more than one island\n",
    "        if uf.comp_cnt == tot: return 1 # only one grid is 1\n",
    "\n",
    "        dfn = defaultdict(int)\n",
    "        low = defaultdict(int)\n",
    "        time = 1\n",
    "\n",
    "        def tarjan(x, y, fa):\n",
    "            nonlocal time\n",
    "            dfn[(x, y)] = low[(x, y)] = time\n",
    "            time += 1\n",
    "\n",
    "            cnt = 0\n",
    "            for dx, dy in pairwise([-1, 0, 1, 0, -1]):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1 and (nx, ny) != fa:\n",
    "                    if not dfn[(nx, ny)]:\n",
    "                        cnt += 1\n",
    "                        if tarjan(nx, ny, (x, y)): return True\n",
    "                        low[(x, y)] = min(low[(x, y)], low[(nx, ny)])\n",
    "                        if dfn[(x, y)] <= low[(nx, ny)]:\n",
    "                            if (x, y) != (sr, sc) or cnt > 1:\n",
    "                                return True\n",
    "                    else:\n",
    "                        low[(x, y)] = min(low[(x, y)], dfn[(nx, ny)])\n",
    "            return False\n",
    "        return 1 if tarjan(sr, sc, (-1, -1)) else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        graph = collections.defaultdict(list)\n",
    "        parent = {i : i for i in range(m * n)}\n",
    "        size = [1] * (m * n)\n",
    "        self.size = 0\n",
    "        def find(node):\n",
    "            path = []\n",
    "            while node != parent[node]:\n",
    "                path.append(node)\n",
    "                node = parent[node]\n",
    "            for p in path:\n",
    "                parent[p] = node \n",
    "            return node \n",
    "        \n",
    "        def union(n1, n2):\n",
    "            p1 = find(n1)\n",
    "            p2 = find(n2)\n",
    "            if p1 != p2:\n",
    "                parent[p1] = p2 \n",
    "                size[p2] += size[p1]\n",
    "                self.size -= 1 \n",
    "        \n",
    "        def neigh(i, j):\n",
    "            for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:\n",
    "                    yield x, y \n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not grid[i][j]:\n",
    "                    continue \n",
    "                self.size += 1 \n",
    "                for x, y in neigh(i, j):\n",
    "                    union(x * n + y, i * n + j)\n",
    "                    graph[i * n + j].append(x * n + y)\n",
    "                    # graph[x * n + y].append(i * n + j)\n",
    "        \n",
    "        dfn = [-1] * (m * n)\n",
    "        low = [-1] * (m * n)\n",
    "        self.found = False \n",
    "        def tarjan(node, time, par):\n",
    "            dfn[node] = time \n",
    "            low[node] = time \n",
    "            child = 0\n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                if dfn[nei] == - 1:\n",
    "                    tarjan(nei, time + 1, node)\n",
    "                    child += 1 \n",
    "                    if (par == - 1 and child > 1) or (par != - 1 and low[nei] >= dfn[node]):\n",
    "                        self.found = True \n",
    "                    low[node] = min(low[node], low[nei])\n",
    "                else:\n",
    "                    low[node] = min(low[node], dfn[nei])\n",
    "        \n",
    "\n",
    "        if self.size != 1:\n",
    "            return 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    if size[find(i * n + j)] == 1:\n",
    "                        return 1 \n",
    "                    tarjan(i * n + j, 0, - 1)\n",
    "                    if self.found:\n",
    "                        return 1 \n",
    "                    break\n",
    "        return 2 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        H,W = len(grid),len(grid[0])\n",
    "        g = collections.defaultdict(list)\n",
    "        \n",
    "        cnt = 0\n",
    "        visited = [False]*(H*W)\n",
    "        DIRs = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "\n",
    "        def to1d(i,j):\n",
    "            return i*W+j\n",
    "\n",
    "        def dfs(i,j):\n",
    "            visited[to1d(i,j)] = True\n",
    "            for di,dj in DIRs:\n",
    "                ni,nj = i+di,j+dj\n",
    "                if 0<=ni<H and 0<=nj<W and grid[ni][nj]==1:\n",
    "                    g[to1d(i,j)].append(to1d(ni,nj))\n",
    "                    if not visited[to1d(ni,nj)]:\n",
    "                        dfs(ni,nj)\n",
    "        \n",
    "        for i,row in enumerate(grid):\n",
    "            for j,n in enumerate(row):\n",
    "                if n == 1 and not visited[to1d(i,j)]:\n",
    "                    cnt += 1\n",
    "                    dfs(i,j)\n",
    "\n",
    "        if cnt!=1: return 0\n",
    "        if not g: return 1\n",
    "        # find articulation point - tarjan's algorithm\n",
    "        # only one connected component\n",
    "        def tarjan(graph):\n",
    "            arti = set() # articulation points\n",
    "            _id = 0\n",
    "            ids = collections.defaultdict(lambda: -1)\n",
    "            lows = collections.defaultdict(lambda: -1)\n",
    "            out = 0\n",
    "\n",
    "            def dfs(i, root, parent):\n",
    "                nonlocal _id, out\n",
    "                ids[i] = lows[i] = _id\n",
    "                _id += 1\n",
    "                out += int(parent==root)\n",
    "\n",
    "                for nei in graph[i]:\n",
    "                    if nei == parent: continue\n",
    "                    if ids[nei] == -1:\n",
    "                        dfs(nei, root, i)\n",
    "                        lows[i] = min(lows[i], lows[nei])\n",
    "                        if ids[i] <= lows[nei]:\n",
    "                            arti.add(i)\n",
    "                    else:\n",
    "                        lows[i] = min(lows[i], ids[nei])\n",
    "\n",
    "\n",
    "            for i in graph.keys():\n",
    "                if ids[i] == -1:\n",
    "                    out = 0\n",
    "                    dfs(i, i, -1)\n",
    "                    if i in arti and out<=1:\n",
    "                        arti.remove(i)\n",
    "\n",
    "            return arti\n",
    "\n",
    "\n",
    "        return 1 if tarjan(g) else 2\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDays(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        graph = collections.defaultdict(list)\n",
    "        parent = {i : i for i in range(m * n)}\n",
    "        size = [1] * (m * n)\n",
    "        self.size = 0\n",
    "        def find(node):\n",
    "            path = []\n",
    "            while node != parent[node]:\n",
    "                path.append(node)\n",
    "                node = parent[node]\n",
    "            for p in path:\n",
    "                parent[p] = node \n",
    "            return node \n",
    "        \n",
    "        def union(n1, n2):\n",
    "            p1 = find(n1)\n",
    "            p2 = find(n2)\n",
    "            if p1 != p2:\n",
    "                parent[p1] = p2 \n",
    "                size[p2] += size[p1]\n",
    "                self.size -= 1 \n",
    "        \n",
    "        def neigh(i, j):\n",
    "            for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:\n",
    "                    yield x, y \n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not grid[i][j]:\n",
    "                    continue \n",
    "                self.size += 1 \n",
    "                for x, y in neigh(i, j):\n",
    "                    union(x * n + y, i * n + j)\n",
    "                    graph[i * n + j].append(x * n + y)\n",
    "                    # graph[x * n + y].append(i * n + j)\n",
    "        \n",
    "        dfn = [-1] * (m * n)\n",
    "        low = [-1] * (m * n)\n",
    "        self.found = False \n",
    "        def tarjan(node, time, par):\n",
    "            dfn[node] = time \n",
    "            low[node] = time \n",
    "            child = 0\n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                if dfn[nei] == - 1:\n",
    "                    tarjan(nei, time + 1, node)\n",
    "                    child += 1 \n",
    "                    if (par == - 1 and child > 1) or (par != - 1 and low[nei] >= dfn[node]):\n",
    "                        self.found = True \n",
    "                    low[node] = min(low[node], low[nei])\n",
    "                else:\n",
    "                    low[node] = min(low[node], dfn[nei])\n",
    "        \n",
    "\n",
    "        if self.size != 1:\n",
    "            return 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    if size[find(i * n + j)] == 1:\n",
    "                        return 1 \n",
    "                    tarjan(i * n + j, 0, - 1)\n",
    "                    if self.found:\n",
    "                        return 1 \n",
    "                    break\n",
    "        return 2 \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
